package com.yanceysong.codetop.s81_s90;

import com.yanceysong.common.TreeNode;

import java.util.*;


public class S83_Mid_662_二叉树最大宽度 {

    /**
     * .题目: 662. 二叉树最大宽度
     * .链接: <a href="https://leetcode.cn/problems/maximum-width-of-binary-tree/">...</a>
     * <p>
     * .描述:
     * .给定一棵二叉树, 其某一层的“宽度”定义为该层最左与最右非空节点在一棵虚拟完全二叉树中的位置索引差值 + 1。
     * .缺失的节点也要计入跨度。
     * <p>
     * .示例:
     * .输入: [1,3,2,5,3,null,9]
     * .第三层的虚拟索引从 4 到 7 => 宽度 = 7 - 4 + 1 = 4
     * .输出: 4
     * <p>
     * .核心标签: 树 / 深度优先搜索 / 虚拟下标模拟 / 映射记录
     * <p>
     * .DFS 思路步骤:
     * .1. 给根节点分配一个起始下标 index = 1 (从1或0开始都可, 统一即可)。
     * .2. 若当前节点下标为 idx:
     * .   - 左孩子下标 = idx * 2
     * .   - 右孩子下标 = idx * 2 + 1
     * .3. 使用深度 depth 递归时:
     * .   - 记录该深度第一遇到的节点下标 (firstIndexAtDepth)。
     * .   - 当前宽度 = idx - firstIndexAtDepth + 1。
     * .4. 递归左右子树, 取最大值。
     * <p>
     * .关键洞察:
     * .- 宽度不是该层真实节点数量, 稀疏结构需用“完全二叉树下标”补洞。
     * .- 只需保存每层第一个出现的节点下标即可即时计算当前宽度, 无需存整层。
     * .- 使用 long 防止大树溢出 (理论上高度很大才风险)。
     * <p>
     * .ASCII 图:
     * .             1(1)
     * .           /      \
     * .        3(2)      2(3)
     * .       /  \         \
     * .    5(4) 3(5)       9(7)
     * .第三层索引: 4,5,null,7 -> 宽度 = 7 - 4 + 1 = 4
     * <p>
     * .复杂度:
     * .时间 O(n): 每节点访问一次。
     * .空间 O(h): 递归栈高度 (最坏退化链 O(n)) + 记录首下标的 Map O(h)。
     * <p>
     * .边界:
     * .- 空树返回 0
     * .- 单节点返回 1
     * .- 极度稀疏可能产生大跨度
     */
    public int widthOfBinaryTree(TreeNode root) {
        return widthOfBinaryTreeDFS(root);
    }

    /**
     * .DFS 版本: 记录每一层最左(首)出现的节点下标
     * .@param root 根
     * .@return 最大宽度
     */
    public int widthOfBinaryTreeDFS(TreeNode root) {
        Map<Integer, Long> firstIndexAtDepth = new HashMap<>();
        return (int) dfsComputeWidth(root, 1, 1L, firstIndexAtDepth);
    }

    /**
     * .深度优先递归
     * .@param node   当前节点
     * .@param depth  当前深度 (根为1)
     * .@param index  当前节点在虚拟完全二叉树中的下标
     * .@param firstIndexAtDepth 记录各层最左节点下标
     * .@return 以当前节点为根的子树内的最大宽度
     */
    private long dfsComputeWidth(TreeNode node,
                                 int depth,
                                 long index,
                                 Map<Integer, Long> firstIndexAtDepth) {
        if (node == null) {
            return 0;
        }
        // 若该层首次出现, 记录其下标
        firstIndexAtDepth.putIfAbsent(depth, index);
        // 当前层宽度 = 当前节点下标 - 本层最左节点下标 + 1
        long currentWidth = index - firstIndexAtDepth.get(depth) + 1;

        // 递归左右子树, 分别传入对应的虚拟下标
        long leftMaxWidth = dfsComputeWidth(node.left, depth + 1, index * 2, firstIndexAtDepth);
        long rightMaxWidth = dfsComputeWidth(node.right, depth + 1, index * 2 + 1, firstIndexAtDepth);

        // 返回三者最大值: 当前层宽度 vs 左子树最大宽度 vs 右子树最大宽度
        return Math.max(currentWidth, Math.max(leftMaxWidth, rightMaxWidth));
    }

    // ================== 测试部分 ==================
    public static void main(String[] args) {
        S83_Mid_662_二叉树最大宽度 solver = new S83_Mid_662_二叉树最大宽度();

        System.out.println("=== 二叉树最大宽度测试开始 ===");

        // 测试1: 官方示例
        testCase(solver, new Integer[]{1, 3, 2, 5, 3, null, 9}, 4, "官方示例1");

        // 测试2: 官方示例2
        testCase(solver, new Integer[]{1, 3, 2, 5}, 2, "官方示例2");

        // 测试3: 单节点
        testCase(solver, new Integer[]{1}, 1, "单节点");

        // 测试4: 左链
        testCase(solver, new Integer[]{1, 2, null, 3, null, 4, null}, 1, "单侧链状(左)");

        // 测试5: 稀疏造成宽度扩张
        // 构造: 在第三层远端分布节点
        testCase(solver, new Integer[]{1, 2, 3, 4, null, null, 7, 8, null, null, null, null, null, null, 15}, 8, "稀疏扩张");

        // 测试6: 完全二叉树 (深度4)
        testCase(solver, buildCompleteTreeArray(4), (int) Math.pow(2, 3), "完全二叉树深度4");

        // 随机一致性测试 (widthOfBinaryTree 与 widthOfBinaryTreeDFS 应一致)
        randomConsistencyTest(solver, 50, 8);

        // 性能测试
        performanceTest(solver, 11);

        System.out.println("=== 所有测试完成 ===");
    }

    // 构建完全二叉树的数组表示
    private static Integer[] buildCompleteTreeArray(int depth) {
        if (depth <= 0) return new Integer[0];
        int total = (int) Math.pow(2, depth) - 1;
        Integer[] arr = new Integer[total];
        for (int i = 0; i < total; i++) {
            arr[i] = i + 1;
        }
        return arr;
    }

    // 测试单用例
    private static void testCase(S83_Mid_662_二叉树最大宽度 solver,
                                 Integer[] levelArray,
                                 int expected,
                                 String desc) {
        TreeNode root = buildTree(levelArray);
        int actual = solver.widthOfBinaryTree(root);
        System.out.printf("%s: 输入=%s -> 输出=%d (期望=%d)%n",
                desc, Arrays.toString(levelArray), actual, expected);
        assert actual == expected : desc + " DFS主入口结果不匹配";
        int actualDFS = solver.widthOfBinaryTreeDFS(root);
        assert actualDFS == expected : desc + " DFS直接调用结果不匹配";
    }

    // 随机一致性测试
    private static void randomConsistencyTest(S83_Mid_662_二叉树最大宽度 solver, int cases, int maxDepth) {
        Random rand = new Random(42);
        System.out.println("随机一致性测试开始...");
        for (int c = 1; c <= cases; c++) {
            // 随机生成数组表示 (按层)，随机决定节点是否为 null
            int depth = 2 + rand.nextInt(Math.max(1, maxDepth - 1));
            int size = (int) Math.pow(2, depth) - 1;
            Integer[] arr = new Integer[size];
            arr[0] = rand.nextInt(50);
            for (int i = 1; i < size; i++) {
                // 以一定概率为空 (避免整棵树全满)
                arr[i] = rand.nextDouble() < 0.25 ? null : rand.nextInt(100);
            }
            TreeNode root = buildTree(arr);
            int w1 = solver.widthOfBinaryTree(root);
            int w2 = solver.widthOfBinaryTreeDFS(root);
            assert w1 == w2 : "随机测试不一致: w1=" + w1 + ", w2=" + w2;
        }
        System.out.println("✓ 随机一致性测试通过");
    }

    // 性能测试
    private static void performanceTest(S83_Mid_662_二叉树最大宽度 solver, int depth) {
        Integer[] arr = buildCompleteTreeArray(depth);
        TreeNode root = buildTree(arr);
        long t1 = System.currentTimeMillis();
        int ans1 = solver.widthOfBinaryTree(root);
        long t2 = System.currentTimeMillis();
        int ans2 = solver.widthOfBinaryTreeDFS(root);
        long t3 = System.currentTimeMillis();
        System.out.printf("性能测试(深度=%d, 节点≈%d): 主入口=%d 时间=%dms | 直接DFS=%d 时间=%dms%n",
                depth, arr.length, ans1, (t2 - t1), ans2, (t3 - t2));
        assert ans1 == Math.pow(2, depth - 1) : "性能测试结果异常";
    }

    // 根据层序数组构造二叉树 (null 表示缺失)
    private static TreeNode buildTree(Integer[] arr) {
        if (arr == null || arr.length == 0 || arr[0] == null) return null;
        TreeNode root = new TreeNode(arr[0]);
        Deque<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root);
        int i = 1;
        while (i < arr.length && !queue.isEmpty()) {
            TreeNode parent = queue.poll();
            // 左孩子
            if (i < arr.length && arr[i] != null) {
                parent.left = new TreeNode(arr[i]);
                queue.offer(parent.left);
            }
            i++;
            // 右孩子
            if (i < arr.length && arr[i] != null) {
                parent.right = new TreeNode(arr[i]);
                queue.offer(parent.right);
            }
            i++;
        }
        return root;
    }
}
